package oop.ex1.dataStructures;

import java.util.Iterator;
import java.util.Random;

/**
 * An abstract queue of comparable objects.
 * Supports push,peek,poll, size and random iteration.
 * @author OOP
 */
public abstract class AbstractComparableQueue {

	///////////////////////////////////////////////////////
	///////////////////////Constants///////////////////////
	///////////////////////////////////////////////////////

	/**
	 * Default size of the queue.
	 */
	protected static final int DEFAULT_INITIAL_CAPACITY = 32;
	
	/**
	 * Default pointer location at initilazation.
	 * _dataLocation is always set to point the data. At starting location with no queue elements it is set to -1 
	 */
	protected static final int DEFAULT_STARTING_LOCATION = -1;

	///////////////////////////////////////////////////////
	//////////////////////Data Members/////////////////////
	///////////////////////////////////////////////////////

	/**
	 * Elements in the queue.
	 */
	protected ComparableObject[] _queue;

	/**
	 * Represents the location which the next data will be 
	 * inserted (will always be one step ahead of the actual data).
	 */
	protected int _size;

	///////////////////////////////////////////////////////
	/////////////////////Public methods////////////////////
	///////////////////////////////////////////////////////

	/**
	 * @throws EmptyQueueException if queue is empty.
	 * @return The top element in the queue (without removing it).
	 */
	public abstract ComparableObject peek() throws EmptyQueueException;

	/**
	 * @throws EmptyQueueException if queue is empty.
	 * @return The top element in the queue (and remove it).
	 */
	public abstract ComparableObject poll() throws EmptyQueueException;

	/**
	 * Push obj into the queue.
	 * @param obj Object to push to queue.
	 */
	public abstract void push(ComparableObject obj);


	/**
	 * Extends the queue by coping it into a bigger array when the queue reaches 
	 * it's maximum size.
	 * @param prevQueue The previous array which has reached it's maximum size.
	 * @param newQueueSize The size of the new array.
	 */
	public ComparableObject[] extendQueue(ComparableObject[] prevQueue,int newQueueSize) {
		ComparableObject[] _tmpQueue = new ComparableObject[newQueueSize];
		for(int i=0;i<_size;i++) { // Iterate and copy the array.
			_tmpQueue[i] = prevQueue[i];
		}
		return _tmpQueue;
	}


	public Iterator RandomIterator() {
		return new RandomIterator();
	}

	public Iterator RandomIterator(long seed) {
		return new RandomIterator(seed);
	}


	///////////////////////////////////////////////////////
	/////////////////////Inner Classes/////////////////////
	///////////////////////////////////////////////////////

	private class RandomIterator implements Iterator {

		//////////////////////Data Members/////////////////////

		/**
		 * A boolean array that is used for marking if an object as been 
		 * iterated already.
		 */
		boolean [] _itratorMarker;

		/**
		 * 
		 */
		Random _randomizer;

		/**
		 * 
		 */
		public RandomIterator() {
			_itratorMarker = new boolean[_queue.length];
			_randomizer = new Random();
		}

		/////////////////////Public methods////////////////////

		/**
		 * 
		 * @param seed
		 */
		public RandomIterator(long seed) {
			_itratorMarker = new boolean[_queue.length];
			_randomizer = new Random(seed);
		}

		/**
		 * 
		 */
		public boolean hasNext(){
			if (_size == DEFAULT_INITIAL_CAPACITY){
				return false;
			}
			for (int i=0; i<=_size ; i++ ) {
				if (!checkMarker(i)) {
					return true;
				}
			}
			return false;
		}
		
		/**
		 * 
		 */
		public ComparableObject next() {
			int randomInt = _randomizer.nextInt(_size+1);
			boolean hasNext = this.hasNext();
			while(hasNext) {
				if(!checkMarker(randomInt)){
					_itratorMarker[randomInt]=true;
					return _queue[randomInt];
				}
				randomInt = _randomizer.nextInt(_size+1);
			}
			return null;
		}
 
		public void remove() {
			// Empty as instructed
		}

		/////////////////////Private methods////////////////////

		/**
		 * 
		 */
		private boolean checkMarker (int location){
			return _itratorMarker[location];
		}

	}









}



